package com.ujs.code.removeElement;

/**
 * @author zhangshihao
 * @create 2023-09-15 15:53
 * 844. 比较含退格的字符串
 */
public class BackspaceCompare {
    public static void main(String[] args) {
        BackspaceCompare backspaceCompare = new BackspaceCompare();
        String s = "#a#c";
        String t = "a##c";
        boolean b = backspaceCompare.backspaceCompare2(s, t);
        System.out.println(b);
    }

    /**
     * 双指针法
     *一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
     *
     * 具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
     * 若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；
     * 若该字符为普通字符：
     *  若 skip 为 0，则说明当前字符不需要删去；
     *  若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。
     * 这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，
     * 直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare2(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i > 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j > 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }


    /**
     * 输入：s = "ab#c", t = "ad#c"
     * 输出：true
     * 解释：s 和 t 都会变成 "ac"。
     *
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        String s1 = this.process(s);
        System.out.println("s1 = " + s1);
        String s2 = this.process(t);
        System.out.println("s2 = " + s2);
        return s1.equals(s2);
    }

    private String process(String s) {
        int count = 0;
        int m = s.length();
        while (count < m) {
            int n = s.length();
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '#') {
                    if (i == 0) {
                        s = s.replaceFirst("#", "");
                    } else {
                        s = s.replaceFirst(s.charAt(i - 1) + "#", "");
                    }
                    break;
                }
            }
            count++;
        }
        return s;
    }
}
